#include <iostream>
using namespace std;

class LinkedList {
public:
    struct Node {
        int data;
        Node* next;

        Node(int a = 0, Node* b = nullptr)
                :data(a), next(b)
        {}
    };

private:
    Node* head;
    int size;

public:
    LinkedList();
    LinkedList(const LinkedList& rhs);
    LinkedList(int const a[], int n);
    LinkedList(int n, int value);
    ~LinkedList();

    int getSize()const { return size; }
    void Print() const;

    void insert(int pos, int value);
    void remove(int pos);

    int& at(int pos);
    const int& at(int pos) const;

    void modify(int pos, int newValue);
    LinkedList::Node* advance(int pos) const;

    //赋值运算符重载
    LinkedList& operator = (const LinkedList& rhs);
    LinkedList& operator += (const LinkedList& rhs);

    //方括号运算符重载
    int& operator [] (int pos);
    const int& operator [] (int pos) const;

    friend const LinkedList operator + (const LinkedList& lhs, const LinkedList& rhs);
    //关系运算符重载，按照字典序比较顺序表
    friend bool operator == (const LinkedList& lhs, const LinkedList& rhs);
    friend bool operator != (const LinkedList& lhs, const LinkedList& rhs);
    friend bool operator < (const LinkedList& lhs, const LinkedList& rhs);
    friend bool operator <= (const LinkedList& lhs, const LinkedList& rhs);
    friend bool operator > (const LinkedList& lhs, const LinkedList& rhs);
    friend bool operator >= (const LinkedList& lhs, const LinkedList& rhs);

    //流输出运算符重载，所有内容输出一行，每个数据后面接一个空格
    friend ostream& operator << (ostream& os, const LinkedList& rhs);

};

LinkedList::LinkedList()
        :head(nullptr), size(0)
{}

LinkedList::LinkedList(const LinkedList& rhs)
{
    if (this != &rhs) {
        struct Node *prhs = rhs.head;
        struct Node *tmp = nullptr, *rear = nullptr;
        head = nullptr;                 //一定要初始化
        size = rhs.size;                //获取样本的长度
        while (prhs != nullptr) {       //只要样本没有扫描完
            tmp = new Node(prhs->data); //获取样本结点的数据
            if (head == nullptr) {      //当前链表尚为空
                head = rear = tmp;      //既是头结点,也是尾结点
            }
            else {                      //当前链表不为空
                rear->next = tmp;       //加入到最后
                rear = tmp;             //作为尾结点
            }
            prhs = prhs->next;          //获取样本中的下一个结点
        }
    }
}

//原生数组构造函数，构造一个内容与给定数组相同的链表
LinkedList::LinkedList(int const a[], int n)
{
    struct Node *temp = nullptr;
    struct Node *rear = nullptr;//尾节点
    head = nullptr;
    for (int i = 0; i < n; i++) {
        temp = new Node(a[i]);
        if (head == nullptr) {
            head = rear = temp;
            head->next = nullptr;
        }
        else {
            rear->next = temp;
            rear = temp;
        }
    }
    size = n;
}

//填充构造函数，构造一个内容为n个value的链表
LinkedList::LinkedList(int n, int value)
{
    Node *p = head;
    Node *temp, *rear = nullptr;
    head = nullptr;
    for (int i = 1; i <= n; i++) {
        temp = new Node(value);
        if (head == nullptr) {
            head = rear = temp;
            head->next = nullptr;
        }
        else {
            rear->next = temp;
            rear = temp;
        }
    }
    size = n;
}

//析构函数，一定要自行实现，否则有内存泄漏
LinkedList::~LinkedList()
{
    Node *p = head;
    while (p != nullptr) {
        head = p->next;
        delete p;
        p = head;
    }
    size = 0;
}

void LinkedList::Print() const
{
    Node *p = head;
    while (p != nullptr) {
        cout << p->data << "\t";
        p = p->next;
    }
    cout << endl;
}

void LinkedList::insert(int pos, int value)
{
    int i = 0;
    Node *p = head, *prev = nullptr;
    while (p != nullptr && i < pos) {
        prev = p;
        p = p->next;
        ++i;
    }
    Node* tmp = new Node(value);
    if (prev == nullptr) {
        if (p == nullptr) {
            head = tmp;
        }
        else {
            tmp->next = head;
            head = tmp;
        }
    }
    else {
        prev->next = tmp;
        tmp->next = p;
    }
    ++size;
}

void LinkedList::remove(int pos)
{
    int i = 0;
    Node* p = head, * prev = nullptr;
    while (p != nullptr && i < pos) {
        prev = p;
        p = p->next;
        ++i;
    }
    if (prev == nullptr) {
        if (p == nullptr) {
            return;
        }
        else {
            head = p->next;
            delete p;
            --size;
        }
    }
    else {
        if (p == nullptr) {
            return;
        }
        else {
            prev->next = p->next;
            delete p;
            --size;
        }
    }
}

int& LinkedList::at(int pos)
{
    int i = 0;
    Node* p = head;
    while (p != nullptr && i < pos) {
        p = p->next;
        ++i;
    }
    if (p != nullptr)
        return p->data;
    else
        throw "error: pos out of range.";

}

const int& LinkedList::at(int pos) const
{
    int i = 0;
    Node* p = head;
    while (p != nullptr && i < pos) {
        p = p->next;
        ++i;
    }
    if (p != nullptr)
        return p->data;
    else
        throw "error: pos out of range.";

}

void LinkedList::modify(int pos, int newValue)
{
    int i = 0;
    Node* p = head;
    while (p != nullptr && i < pos) {
        p = p->next;
        ++i;
    }
    if (p != nullptr)
        p->data = newValue;
    else
        throw "error: pos out of range.";
}

LinkedList::Node* LinkedList::advance(int pos) const
{
    int i = 0;
    Node* p = head;
    while (p != nullptr && i < pos) {
        p = p->next;
        ++i;
    }
    if (p != nullptr)
        return p;
    else
        throw "error: pos out of range.";
}

//赋值运算符重载: 效率较高的实现方法,在左操作数中直接改
LinkedList& LinkedList::operator = (const LinkedList& rhs)
{
    if (this != &rhs) {
        Node *plprev = nullptr, *pl = this->head, *pr = rhs.head;
        while (pl != nullptr && pr != nullptr) {    //如果两个链表都不为空
            pl->data = pr->data;                    //直接把结点的数据进行赋值
            plprev = pl; pl = pl->next;             //要记录当前链表的两个相邻指针
            pr = pr->next;
        }
        if (pl != nullptr) {            //若左链表比右链表长,则应释放左链表中多余的结点
            plprev->next = nullptr;     //先让左链表中成为一个完整的链表

            while (pl != nullptr) {     //释放后面多余的结点
                Node *p = pl->next;
                delete pl;
                pl = p;
            }
        }
        while (pr != nullptr) {         //若右链表比左链表长,则应向左链表中插入右链表多余的结点
            Node *tmp = new Node(pr->data);//根据多余结点的数据生成新结点
            if (plprev == nullptr) {        //若左链表根本就是一个空链表
                this->head = tmp;           //插入的第一个结点作为头结点
                plprev = tmp;               //同时记为尾结点
            }
            else {                          //若左链表之前有其他结点
                plprev->next = tmp;         //接在最后
                plprev = tmp;               //同时作为最后一个结点
            }
            pr = pr->next;
        }
        size = rhs.size;
    }
    return *this;
}

//赋值运算符重载:效率较低的实现方法,先释放现有,再根据右操作数重新生成
//LinkedList& LinkedList::operator = (const LinkedList& rhs)
//{
//    if (this != &rhs) {
//        // step 1: delete *this
//        Node* p = head;
//        while (p != nullptr) {
//            head = p->next;
//            delete p;
//            p = head;
//        }
//
//        // step 2: copy rhs
//        struct Node* prhs = rhs.head;
//        struct Node* temp = nullptr, * last = nullptr;
//        head = nullptr;  //一定要初始化
//        while (prhs != nullptr) {
//            temp = new Node(prhs->data);
//            if (head == nullptr) {
//                head = last = temp;
//            }
//            else {
//                last->next = temp;
//                last = temp;
//            }
//            prhs = prhs->next;
//        }
//        size = rhs.size;
//    }
//    return *this;
//}

LinkedList& LinkedList::operator += (const LinkedList& rhs)
{
    return *this = *this + rhs;
}

//方括号运算符重载
int& LinkedList::operator [] (int pos)
{
    return this->at(pos);
}
const int& LinkedList::operator [] (int pos) const
{
    return this->at(pos);
}

const LinkedList operator + (const LinkedList& lhs, const LinkedList& rhs)
{
    LinkedList result(lhs);

    //如下找到链表result的最后一个结点rear
    LinkedList::Node *p = result.head, *rear = nullptr;
    while (p != nullptr) {
        rear = p;
        p = p->next;
    }

    //把链表rhs中的结点链入到result的后面
    p = rhs.head;
    while (p != nullptr) {
        LinkedList::Node *tmp = new LinkedList::Node(p->data);
        rear->next = tmp;
        rear = tmp;
        p = p->next;
    }
    return result;
}

//关系运算符重载，按照字典序比较顺序表
bool operator == (const LinkedList& lhs, const LinkedList& rhs)
{
    LinkedList::Node *pl = lhs.head, *pr = rhs.head;
    while (pl != nullptr && pr != nullptr
           && pl->data == pr->data) {
        pl = pl->next;
        pr = pr->next;
    }
    return pl == nullptr && pr == nullptr;
}
bool operator != (const LinkedList& lhs, const LinkedList& rhs)
{
    return !(lhs == rhs);
}
bool operator < (const LinkedList& lhs, const LinkedList& rhs) {
    LinkedList::Node *pleft = lhs.head, *pright = rhs.head;
    while (true) {
        if (pleft == nullptr) {
            if (pright == nullptr) return false;
            else return true;
        }
        else {
            if (pright == nullptr) return false;
            else {
                if (pleft->data < pright->data) return true;
                else if (pleft->data > pright->data) return false;
                else {
                    pleft = pleft->next;
                    pright = pright->next;
                }
            }
        }
    }
}
bool operator <= (const LinkedList& lhs, const LinkedList& rhs)
{
    return !(rhs < lhs);
}
bool operator > (const LinkedList& lhs, const LinkedList& rhs)
{
    return rhs < lhs;
}
bool operator >= (const LinkedList& lhs, const LinkedList& rhs)
{
    return !(lhs < rhs);
}

//流输出运算符重载，所有内容输出一行，每个数据后面接一个空格
ostream& operator << (ostream& os, const LinkedList& rhs)
{
    LinkedList::Node* p = rhs.head;
    while (p != nullptr) {
        os << p->data << "\t";
        p = p->next;
    }
    os << endl;
    return os;
}

int main() {
    int A[]  {100, 200, 400, 800, 1600, 1800, 2000};
    LinkedList a, b(A, size(A)), c(A, 5);

    cout << a.getSize() << ": "; a.Print(); cout << endl;
    cout << b.getSize() << ": "; b.Print(); cout << endl;
    cout << c.getSize() << ": "; c.Print(); cout << endl;

    cout << "b + c:\t" << (b + c);
    a = b + c; cout << "a:\t" << a;
    //b = b + c; cout << "b:\t" << b << endl;
    b += c; cout << "b:\t" << b;

    cout << "a:\t" << a;
    cout << "c:\t" << c;
    cout << "a == b:\t" << boolalpha << (a == b) << endl;
    cout << "a == c:\t" << boolalpha << (a == c) << endl;
    cout << "a <  c:\t" << boolalpha << (a <  c) << endl;
    cout << "c <  a:\t" << boolalpha << (c <  a) << endl;
    cout << "a <  a:\t" << boolalpha << (a <  a) << endl;








//    a = b;
//    cout << a.getSize() << ": "; a.Print(); cout << endl;
//    a = c;
//    cout << a.getSize() << ": "; a.Print(); cout << endl;






//    LinkedList c(b), d(8, 6);
//    cout << c.getSize() << ": ";
//    c.Print();
//    cout << endl;
//
//    cout << d.getSize() << ": ";
//    d.Print();
//    cout << endl;
//
//    a.insert(10, 111);
//    a.insert(0, 222);
//    a.insert(10, 333);
//    a.Print();
//    cout << endl;
//
//    for (int i = 0; i < b.getSize(); ++i)
//        cout << b.at(i) << "\t";
//    cout << endl;

    return 0;
}